|
Fitness proportionate selection, also known as roulette wheel selection, is a genetic operator used in genetic algorithms for selecting potentially useful solutions for recombination. In fitness proportionate selection, as in all selection methods, the fitness function assigns a fitness to possible solutions or chromosomes. This fitness level is used to associate a probability of selection with each individual chromosome. If is the fitness of individual in the population, its probability of being selected is , where is the number of individuals in the population. This could be imagined similar to a Roulette wheel in a casino. Usually a proportion of the wheel is assigned to each of the possible selections based on their fitness value. This could be achieved by dividing the fitness of a selection by the total fitness of all the selections, thereby normalizing them to 1. Then a random selection is made similar to how the roulette wheel is rotated. While candidate solutions with a higher fitness will be less likely to be eliminated, there is still a chance that they may be. Contrast this with a less sophisticated selection algorithm, such as truncation selection, which will eliminate a fixed percentage of the weakest candidates. With fitness proportionate selection there is a chance some weaker solutions may survive the selection process; this is an advantage, as though a solution may be weak, it may include some component which could prove useful following the recombination process. The analogy to a roulette wheel can be envisaged by imagining a roulette wheel in which each candidate solution represents a pocket on the wheel; the size of the pockets are proportionate to the probability of selection of the solution. Selecting N chromosomes from the population is equivalent to playing N games on the roulette wheel, as each candidate is drawn independently. Other selection techniques, such as stochastic universal sampling〔Bäck, Thomas, ''Evolutionary Algorithms in Theory and Practice'' (1996), p. 120, Oxford Univ. Press〕 or tournament selection, are often used in practice. This is because they have less stochastic noise, or are fast, easy to implement and have a constant selection pressure (1996 ). The naive implementation is carried out by first generating the cumulative probability distribution (CDF) over the list of individuals using a probability proportional to the fitness of the individual. A uniform random number from the range 〕 ==Pseudocode== For example, if you have a population with fitnesses (2, 3, 4 ), then the sum is 10 (1 + 2 + 3 + 4). Therefore, you would want the probabilities or chances to be (2/10, 3/10, 4/10 ) or (0.2, 0.3, 0.4 ). If you were to visually normalize this between 0.0 and 1.0, it would be grouped like below with (= 1/10, green = 2/10, blue = 3/10, black = 4/10 ): 0.1 ] 0.2 \ 0.3 / 0.4 \ 0.5 | 0.6 / 0.7 \ 0.8 | 0.9 | 1.0 / Using the above example numbers, this is how to determine the probabilities: sum_of_fitness = 10 previous_probability = 0.0 () = previous_probability + (fitness / sum_of_fitness) = 0.0 + (1 / 10) = 0.1 previous_probability = 0.1 () = previous_probability + (fitness / sum_of_fitness) = 0.1 + (2 / 10) = 0.3 previous_probability = 0.3 () = previous_probability + (fitness / sum_of_fitness) = 0.3 + (3 / 10) = 0.6 previous_probability = 0.6 () = previous_probability + (fitness / sum_of_fitness) = 0.6 + (4 / 10) = 1.0 The last index should always be 1.0 or close to it. Then this is how to randomly select an individual: random_number # Between 0.0 and 1.0 if random_number < 0.1 select else if random_number < 0.3 # 0.3 - 0.1 = 0.2 probability select else if random_number < 0.6 # 0.6 - 0.3 = 0.3 probability select else if random_number < 1.0 # 1.0 - 0.6 = 0.4 probability select end 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fitness proportionate selection」の詳細全文を読む スポンサード リンク
|